πŸ‘©β€πŸ’» 72415. μΉ΄λ“œ 짝 λ§žμΆ”κΈ°

@Seongukbaek Posted July 07, 2022 Β· Updated July 07, 2022 Β· 6 min read

문제

Programmers - μΉ΄λ“œ 짝 λ§žμΆ”κΈ°

πŸ“ Logic

private static int permutate(Card src) { int ret = Integer.MAX_VALUE; // 1λΆ€ν„° 6κΉŒμ§€μ˜ μΉ΄λ“œκ°€ μ‘΄μž¬ν•  수 μžˆλ‹€. for (int n = 1; n <= 6; n++) { // n에 ν•΄λ‹Ήν•˜λŠ” μΉ΄λ“œλ₯Ό μ €μž₯ν•˜λŠ” 리슀트 ArrayList<Card> cards = findNCard(n); // μ„ νƒν•œ μΉ΄λ“œλ“€μ΄ μ—†λŠ” 경우, 패슀 if (cards.isEmpty()) continue; // ν˜„μž¬ μœ„μΉ˜λΆ€ν„° μ„ νƒν•œ μΉ΄λ“œκΉŒμ§€ κ°€κΈ° μœ„ν•œ 거리λ₯Ό 계산 int one = bfs(src, cards.get(0)) + bfs(cards.get(0), cards.get(1)) + 2; // one의 μ—­μˆœμœΌλ‘œ μ§„ν–‰ int two = bfs(src, cards.get(1)) + bfs(cards.get(1), cards.get(0)) + 2; // 뒀집은 μΉ΄λ“œλ₯Ό λ³΄λ“œμ—μ„œ 제거 removeCards(cards); // μž¬κ·€ 호좜 μˆ˜ν–‰ // one으둜 μˆ˜ν–‰ν•œ μΉ΄λ“œ λ’€μ§‘κΈ° 이후, μ»€μ„œκ°€ card.get(1)에 μžˆμ„ λ•Œ 남은 μΉ΄λ“œλ“€μ— λŒ€ν•œ λ’€μ§‘κΈ° μˆ˜ν–‰ ret = Math.min(ret, one + permutate(cards.get(1))); // two둜 μˆ˜ν–‰ν•œ μΉ΄λ“œ λ’€μ§‘κΈ° 이후, μ»€μ„œκ°€ card.get(0)에 μžˆμ„ λ•Œ 남은 μΉ΄λ“œλ“€μ— λŒ€ν•œ λ’€μ§‘κΈ° μˆ˜ν–‰ ret = Math.min(ret, two + permutate(cards.get(0))); // 1번 μΉ΄λ“œμ— λŒ€ν•œ λ’€μ§‘κΈ° μˆ˜ν–‰ ν›„, 2번 μΉ΄λ“œμ— λŒ€ν•œ λ’€μ§‘κΈ° μ§„ν–‰ μ‹œμ—λŠ” 1번 μΉ΄λ“œ 뒀집기에 λŒ€ν•œ 볡원이 ν•„μš”ν•˜λ‹€. restoreCards(cards, n); } if (ret == Integer.MAX_VALUE) return 0; return ret; }
  • μž¬κ·€λ₯Ό μˆ˜ν–‰ν•˜λ©΄μ„œ, λͺ¨λ“  μΉ΄λ“œ λ’€μ§‘κΈ° μˆœμ„œλ₯Ό μ§„ν–‰ν•˜λ©΄μ„œ μ΅œμ†Œ λΉ„μš©μ„ κ³„μ‚°ν•œλ‹€.
  • μΉ΄λ“œμ™€ μΉ΄λ“œ κ°„ 이동 μ‹œ μ΅œμ†Œ μ‘°μž‘ 횟수λ₯Ό κ΅¬ν•˜κΈ° μœ„ν•΄ BFSλ₯Ό μˆ˜ν–‰ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Card { // ν–‰, μ—΄, μ΄λ™ν•˜κΈ° μœ„ν•΄ ν•„μš”ν•œ μ‘°μž‘ 횟수 int r; int c; int count; public Card(int r, int c, int count) { this.r = r; this.c = c; this.count = count; } } class Solution { static int[][] board; static int[][] range = {{ -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }}; public int solution(int[][] board, int r, int c) { this.board = board; return permutate(new Card(r, c, 0)); } private static int permutate(Card src) { int ret = Integer.MAX_VALUE; // 1λΆ€ν„° 6κΉŒμ§€μ˜ μΉ΄λ“œκ°€ μ‘΄μž¬ν•  수 μžˆλ‹€. for (int n = 1; n <= 6; n++) { // n에 ν•΄λ‹Ήν•˜λŠ” μΉ΄λ“œλ₯Ό μ €μž₯ν•˜λŠ” 리슀트 ArrayList<Card> cards = findNCard(n); // μ„ νƒν•œ μΉ΄λ“œλ“€μ΄ μ—†λŠ” 경우, 패슀 if (cards.isEmpty()) continue; // ν˜„μž¬ μœ„μΉ˜λΆ€ν„° μ„ νƒν•œ μΉ΄λ“œκΉŒμ§€ κ°€κΈ° μœ„ν•œ 거리λ₯Ό 계산 int one = bfs(src, cards.get(0)) + bfs(cards.get(0), cards.get(1)) + 2; // one의 μ—­μˆœμœΌλ‘œ μ§„ν–‰ int two = bfs(src, cards.get(1)) + bfs(cards.get(1), cards.get(0)) + 2; // 뒀집은 μΉ΄λ“œλ₯Ό λ³΄λ“œμ—μ„œ 제거 removeCards(cards); // μž¬κ·€ 호좜 μˆ˜ν–‰ // one으둜 μˆ˜ν–‰ν•œ μΉ΄λ“œ λ’€μ§‘κΈ° 이후, μ»€μ„œκ°€ card.get(1)에 μžˆμ„ λ•Œ 남은 μΉ΄λ“œλ“€μ— λŒ€ν•œ λ’€μ§‘κΈ° μˆ˜ν–‰ ret = Math.min(ret, one + permutate(cards.get(1))); // two둜 μˆ˜ν–‰ν•œ μΉ΄λ“œ λ’€μ§‘κΈ° 이후, μ»€μ„œκ°€ card.get(0)에 μžˆμ„ λ•Œ 남은 μΉ΄λ“œλ“€μ— λŒ€ν•œ λ’€μ§‘κΈ° μˆ˜ν–‰ ret = Math.min(ret, two + permutate(cards.get(0))); // 1번 μΉ΄λ“œμ— λŒ€ν•œ λ’€μ§‘κΈ° μˆ˜ν–‰ ν›„, 2번 μΉ΄λ“œμ— λŒ€ν•œ λ’€μ§‘κΈ° μ§„ν–‰ μ‹œμ—λŠ” 1번 μΉ΄λ“œ 뒀집기에 λŒ€ν•œ 볡원이 ν•„μš”ν•˜λ‹€. restoreCards(cards, n); } if (ret == Integer.MAX_VALUE) return 0; return ret; } private static int bfs(Card src, Card dest) { boolean[][] visited = new boolean[4][4]; Queue<Card> queue = new LinkedList<>(); queue.add(src); while(!queue.isEmpty()) { Card now = queue.poll(); // λͺ©μ μ§€μ— λ„μ°©ν•œ 경우, μ‘°μž‘ 횟수λ₯Ό λ°˜ν™˜ if (now.r == dest.r && now.c == dest.c) return now.count; for (int i = 0; i < 4; i++) { int nr = now.r + range[i][0], nc = now.c + range[i][1]; if (!isInBoundary(nr, nc)) continue; // λ°©λ¬Έν•˜μ§€ μ•Šμ€ 경우 μ‘°μž‘ 횟수 κ°±μ‹  if (!visited[nr][nc]) { visited[nr][nc] = true; queue.add(new Card(nr, nc, now.count + 1)); } // ctrl을 μ΄μš©ν•΄ μ‘°μž‘ κ°€λŠ₯ν•œ 경우 for (int j = 0; j < 2; j++) { // λ’€μ§‘μ–΄μ§„ μΉ΄λ“œκ°€ μ•„λ‹Œ 경우 μ’…λ£Œ if (board[nr][nc] != 0) break; // ν•œ 번 더 ν•΄λ‹Ή λ°©ν–₯으둜 μ§„ν–‰ν–ˆμ„ λ•Œ 경계λ₯Ό λ²—μ–΄λ‚˜λŠ” κ²½μš°λ„ μ’…λ£Œ if (!isInBoundary(nr + range[i][0], nc + range[i][1])) break; nr += range[i][0]; nc += range[i][1]; } // nr, ncλŠ” 이제 ν•œ λ²ˆμ— 이동할 수 μžˆλŠ” μœ„μΉ˜ if (visited[nr][nc]) continue; visited[nr][nc] = true; queue.add(new Card(nr, nc, now.count + 1)); } } return Integer.MAX_VALUE; } private static boolean isInBoundary(int r, int c) { return r >= 0 && r < 4 && c >= 0 && c < 4; } private static ArrayList<Card> findNCard(int num) { ArrayList<Card> cards = new ArrayList<>(); for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) if (board[i][j] == num) cards.add(new Card(i, j, 0)); return cards; } private static void removeCards(ArrayList<Card> cards) { for (Card card : cards) board[card.r][card.c] = 0; } private static void restoreCards(ArrayList<Card> cards, int num) { for (Card card : cards) board[card.r][card.c] = num; } }

✏️ Review

  • μ²˜μŒμ— κ΅¬ν˜„ν•˜λ €ν•œ μ•„μ΄λ””μ–΄λŠ”, map 에 μΉ΄λ“œ λ²ˆν˜Έλ³„λ‘œ μΉ΄λ“œ μœ„μΉ˜λ₯Ό μ €μž₯ν•˜κ³ , ν˜„μž¬ μ»€μ„œμ—μ„œ κ°€μž₯ κ°€κΉŒμ΄ μžˆλŠ” μΉ΄λ“œλ₯Ό λ’€μ§‘κ³ , ν•΄λ‹Ή μΉ΄λ“œ 짝을 μ°Ύμ•„ μ»€μ„œλ₯Ό μ΄λ™ν•œ ν›„ λ’€μ§‘κ³ λ₯Ό λ°˜λ³΅ν•˜λŠ” λ°©μ‹μ΄μ—ˆλ‹€.

    • μƒκ°ν•΄λ³΄λ‹ˆ μΉ΄λ“œ μˆœμ„œκ°€ μ€‘μš”ν•  수 μžˆκ² λ‹€λΌλŠ” κ±Έ κΉ¨λ‹¬μ•˜κ³ , κ΅¬ν˜„μ„ μ–΄λ–»κ²Œ ν•΄μ•Ό ν•  μ§€ λͺ¨λ₯΄κ² μ–΄μ„œ ... 풀이 μ˜μƒμ„ μ°Έκ³ ν–ˆλ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€